@InProceedings{RibeiroLore:2007:CoGeAp,
               author = "Ribeiro, G. M. and Lorena, Luiz Antonio Nogueira",
          affiliation = "{} and {Instituto Nacional de Pesquisas Espaciais (INPE)}",
                title = "Column Generation Approach for the Point-feature Cartographic 
                         Label Placement Problem",
                 year = "2007",
         organization = "European Conference on Operations Research, 22.",
             keywords = "Combinatorial optimization, Integer programming, Column 
                         generation, Map Labeling, COMPUTA{\C{C}}{\^A}O APLICADA.",
             abstract = "This paper proposes a column generation approach for the 
                         Point-Feature Cartographic Label Placement problem (PFCLP). The 
                         column generation is based on a Lagrangean relaxation with 
                         clusters proposed for problems modeled by conflict graphs. The 
                         PFCLP can be represented by a conflict graph where vertices are 
                         positions for each label and edges are potential overlaps between 
                         labels (vertices). The conflict graph is decomposed into clusters 
                         forming a block diagonal matrix with coupling constraints that is 
                         known as a restricted master problem (RMP) in a Dantzig-Wolfe 
                         decomposition context. The clusters sub-problems are similar to 
                         the PFCLP and are used to generate new improved columns to RMP. 
                         This approach was tested on PFCLP instances presented in the 
                         literature providing in reasonable times better solutions than all 
                         those known and determining optimal solutions for some difficult 
                         large-scale instances.",
  conference-location = "Prague, Czechoslovakia",
      conference-year = "8-11 july",
             language = "en",
           targetfile = "glaydston-lorena-jco.pdf",
        urlaccessdate = "02 maio 2024"
}